package com.learn;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 */

public class num_283 {
    //使用双指针，两者都从头开始遍历，左指针用于记录非0元素的位置，右指针负责寻找非0元素，随后将数据放进左指针中，当右指针遍历完成，左指针开始移动，填入0
    public void moveZeroesBest(int[] nums) {
        if(nums==null) {
            return;
        }
        //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
        int j = 0;
        for(int i=0;i<nums.length;++i) {
            if(nums[i]!=0) {
                nums[j++] = nums[i];
            }
        }
        //非0元素统计完了，剩下的都是0了
        //所以第二次遍历把末尾的元素都赋为0即可
        for(int i=j;i<nums.length;++i) {
            nums[i] = 0;
        }
    }
    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public static void moveZeroes(int[] nums) {
        //长度，左指针，右指针
        int n = nums.length, left = 0, right = 0;
        //当右指针未完成遍历
        while (right < n) {
            //找到需要的数据，将两者进行交换
            if (nums[right] != 0) {
                //交换的时候就已经把0换到了后面
                swap(nums, left, right);
                //交换完成后，左指针++
                left++;
            }
            right++;
        }
    }
    public static void moveZeroesMyself(int[] nums) {
        int local = 0;
        HashMap<Integer, Integer> localNumMap = new HashMap<>();
        for (int num : nums) {
            if (num != 0) {
                localNumMap.put(local, num);
                local++;
            }
        }
        for (Integer integer : localNumMap.keySet()) {
            nums[integer] = localNumMap.get(integer);
        }
        Arrays.fill(nums, localNumMap.size() , nums.length , 0);
//        System.out.println(Arrays.toString(nums));

    }

    public static void main(String[] args) {
        int[] num = {0, 1, 0, 3, 12};
        moveZeroes(num);
    }
}
